package com.ljy.my_study.leetcode.不同的二叉搜索树II;

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.*;

/**
 * @author lijunying
 * @date 2020/7/21 11:25
 */
public class TestMain {

//    给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
//
//    示例：
//
//    输入：3
//    输出：
//            [
//              [1,null,3,2],
//              [3,2,null,1],
//              [3,1,null,null,2],
//              [2,1,3],
//              [1,null,2,null,3]
//            ]
//    解释：
//    以上的输出对应以下 5 种不同结构的二叉搜索树：
//
//            1         3     3      2      1
//            \       /     /      / \      \
//            3     2     1      1   3      2
//            /     /       \                 \
//            2     1         2                 3
//             
//    提示：
//            0 <= n <= 8


    public static void main(String[] args) {
        List<TreeNode> list= new TestMain().generateTrees(3);
        System.out.println(list);
    }

    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> ans = new ArrayList<TreeNode>();
        if (n == 0) {
            return ans;
        }
        return getAns(1, n);

    }

    private List<TreeNode> getAns(int start, int end) {
        List<TreeNode> list=new ArrayList<>();
        if(start>end){
            list.add(null);
            return list;
        }
        if(start==end){
            TreeNode node=new TreeNode(start);
            list.add(node);
            return list;
        }
        for(int i=start;i<=end;i++){
            List<TreeNode> leftList=getAns(start,i-1);
            List<TreeNode> rightList=getAns(i+1,end);
            for(TreeNode left:leftList){
                for(TreeNode right:rightList){
                    TreeNode node=new TreeNode(i);
                    node.left=left;
                    node.right=right;
                    list.add(node);
                }
            }
        }
        return list;
    }
//    public List<TreeNode> generateTrees(int n) {
//        List<TreeNode> ans = new ArrayList<TreeNode>();
//        if (n == 0) {
//            return ans;
//        }
//        return getAns(1, n);
//
//    }
//
//    private List<TreeNode> getAns(int start, int end) {
//        List<TreeNode> ans = new ArrayList<TreeNode>();
//        //此时没有数字，将 null 加入结果中
//        if (start > end) {
//            ans.add(null);
//            return ans;
//        }
//        //只有一个数字，当前数字作为一棵树加入结果中
//        if (start == end) {
//            TreeNode tree = new TreeNode(start);
//            ans.add(tree);
//            return ans;
//        }
//        //尝试每个数字作为根节点
//        for (int i = start; i <= end; i++) {
//            //得到所有可能的左子树
//            List<TreeNode> leftTrees = getAns(start, i - 1);
//            //得到所有可能的右子树
//            List<TreeNode> rightTrees = getAns(i + 1, end);
//            //左子树右子树两两组合
//            for (TreeNode leftTree : leftTrees) {
//                for (TreeNode rightTree : rightTrees) {
//                    TreeNode root = new TreeNode(i);
//                    root.left = leftTree;
//                    root.right = rightTree;
//                    //加入到最终结果中
//                    ans.add(root);
//                }
//            }
//        }
//        return ans;
//    }


//    public List<TreeNode> generateTrees(int n) {
//        List<TreeNode> list=new ArrayList<>();
//        for(int i=1;i<=n;i++){
//            TreeNode node=new TreeNode(i);
//            dfs(list,node,i,n,1,n);
//        }
//        return list;
//    }
//
//    public void dfs(List<TreeNode> list,TreeNode treeNode,int start,int end,int num,int n){
//        if(num==n){
//            list.add(treeNode);
//            return;
//        }
//        int mid=treeNode.val;
//        for(int i=start;i<=end;i++){
//            TreeNode newNode=copyNode(treeNode);
//            TreeNode nextNode=new TreeNode();
//            nextNode.val=i;
//            if(i<mid){
//                newNode.left=nextNode;
//                dfs(list,newNode,start,mid-1,num+1,n);
//            }else {
//                newNode.right=nextNode;
//                dfs(list,newNode,mid+1,start,num+1,n);
//            }
//        }
//    }

    public TreeNode copyNode(TreeNode node){
        if(node==null){
            return null;
        }
        TreeNode newNode=new TreeNode();
        newNode.val=node.val;
        newNode.left=copyNode(node.left);
        newNode.right=copyNode(node.right);
        return newNode;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode() {}
        public TreeNode(int val) { this.val = val; }
        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}